import collections


class WordDistance(object):

    def __init__(self, wordsDict):
        """
        :type wordsDict: List[str]
        """
        self.d = collections.defaultdict(list)
        for index, w in enumerate(wordsDict):
            self.d[w].append(index)

    def shortest(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        min_dist = 3 * 10 ** 4
        index_word1 = self.d[word1]
        index_word2 = self.d[word2]
        index_1 = 0
        index_2 = 0
        while index_1 < len(index_word1) and index_2 < len(index_word2):
            min_dist = min(abs(index_word1[index_1] - index_word2[index_2]), min_dist)
            if min_dist == 1:
                return min_dist
            if index_word1[index_1] < index_word2[index_2]:
                index_1 += 1
            else:
                index_2 += 1
        return min_dist


wordsDict = ["practice", "makes", "perfect", "coding", "makes"]
obj = WordDistance(wordsDict)
print(obj.shortest("coding", "practice"))
print(obj.shortest("makes", "coding"))
